import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author fangkun
 * @create 2022-11-08-9:25
 */
public class MainTest {
    public static void main(String[] args) {
    }

    public static int[] getMaxWindow(int[] arr, int w){
        //滑动窗口最大值

        if(arr == null || w < 1 || arr.length < w){
            return null;
        }

        LinkedList<Integer> qmax = new LinkedList<>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;

        for (int i = 0; i < arr.length; i++) {
            if (!qmax.isEmpty() && arr[i] >= arr[qmax.peekLast()]){
                qmax.pollLast();
            }
            qmax.addLast(i);

            if (qmax.peekFirst() == i - w){
                qmax.pollFirst();
            }

            if (i >= w - 1){
                res[index] = arr[qmax.peekFirst()];
            }

        }


        return res;
    }

    public static int getNum(int[] arr, int num){
        if (arr == null || arr.length == 0){
            return 0;
        }

        LinkedList<Integer> qmax = new LinkedList<>();
        LinkedList<Integer> qmin = new LinkedList<>();

        int L = 0;
        int R = 0;
        int res = 0;

        while (L < arr.length){
            while (R < arr.length){
                if (!qmax.isEmpty() && arr[L] >= arr[qmax.peekLast()]){
                    qmax.pollLast();
                }
                qmax.addLast(L);

                if (!qmin.isEmpty() && arr[L] <= arr[qmin.peekLast()]){
                    qmin.pollLast();
                }
                qmin.addLast(L);

                if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num){
                    break;
                }
                R++;
            }

            res += R-L;

            if (qmin.peekFirst() == L){
                qmin.pollFirst();
            }
            if (qmax.peekFirst() == L){
                qmax.pollFirst();
            }

            L++;
        }

        return res;
    }

    public static int[][] getNearLessNoRepeat(int[] arr){
        //单调栈（无重复数组）
        int[][] res = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[i] < arr[stack.peek()]){
                int popIndex = stack.pop();
                int leftIndex = stack.isEmpty() ? -1 : stack.peek();

                res[popIndex][0]=leftIndex;
                res[popIndex][1]=i;
            }
        }

        while (!stack.isEmpty()){
            int popIndex = stack.pop();
            int leftIndex = stack.isEmpty() ? -1 : stack.peek();

            res[popIndex][0]=leftIndex;
            res[popIndex][1]=-1;
        }

        return res;
    }

    public static int[][] getNearLess(int[] arr){
        int[][] res = new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]){
                List<Integer> popIndex = stack.pop();
                int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
                for(int popi : popIndex){
                    res[popi][0]= leftIndex;
                    res[popi][1]= i;
                }
            }

            if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]){
                stack.peek().add(Integer.valueOf(i));
            } else {
                ArrayList<Integer> arrayList = new ArrayList<>();
                arrayList.add(i);
                stack.push(arrayList);
            }
        }

        while (!stack.isEmpty()){
            List<Integer> popIndex = stack.peek();
            int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);

            for (int popi : popIndex){
                res[popi][0]= leftIndex;
                res[popi][1]= -1;
            }
        }
        return res;
    }
}
